from typing import List

"""
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]"""


class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        def dfs(list2, start):
            if len(list2) == len(nums):
                res.append(list2.copy())
                return
            for i in range(len(nums)):
                if i > 0 and nums[i] == nums[i - 1] and i - 1 not in start:
                    continue
                if (i in start):
                    continue
                list2.append(nums[i])
                start.append(i)
                dfs(list2, start)
                list2.pop()
                start.pop()

        dfs([], [])
        return res


lll = Solution()
print(lll.permute([1, 1, 2]))
